'''
https://leetcode.cn/problems/closest-binary-search-tree-value
https://leetcode.cn/problems/closest-binary-search-tree-value-ii
'''
import heapq
from typing import Optional, List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        res = root.val
        diff = abs(target - root.val)
        def f(root):
            if not root:
                return
            nonlocal res, diff
            d = abs(root.val - target)
            if d < diff or (d == diff and root.val < res):
                res = root.val
                diff = d
            if root.val < target:
                f(root.right)
            elif root.val > target:
                f(root.left)
        f(root)
        return res
    def closestValue2(self, root: Optional[TreeNode], target: float) -> int:
        res = root.val
        diff = abs(target - root.val)
        while root:
            if root.val == target:
                return root.val
            d = abs(root.val - target)
            if d < diff or (d == diff and root.val < res):
                res = root.val
                diff = d
            if root.val < target:
                root = root.right
            else:
                root = root.left
        return res

    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
        pq = []
        def f(root):
            if not root:
                return
            d = abs(root.val - target)
            if len(pq) < k:
                heapq.heappush(pq, (-d, root.val))
            elif d < -pq[0][0]:
                heapq.heapreplace(pq, (-d, root.val))
            f(root.right)
            f(root.left)
        f(root)
        return [v for _, v in pq]